package data_structure.rbtree001.data;

import java.util.ArrayList;
import java.util.List;

/**
 * 红黑树对象
 */
public class RbTree {
    /* 根节点 */
    private Node root;

    /* 插入新节点处理 */
    public void insert(Node param) {
        // 判断，根节点是否是空
        if (null == root) {
            root = param;
        }else {
            // 插入处理
            // 寻找子节点
            Node leaf = findLeafNode(root, param);
            if (leaf.getValue() >= param.getValue()) {
                leaf.setLeft(param);
            } else {
                leaf.setRight(param);
            }
            // 变化节点，进行平衡
            this.change(param);
        }
        // 根节点固定黑色
        this.root.setRed(false);
    }

    /**
     * 变化节点，进行平衡
     */
    public void change(Node param) {
        // 遍历处理
        while (null != param && param != root && param.getParent().isRed()){
            // 叔叔节点
            Node borthorParent = param.getParent().getBrother();
            // 叔叔是红色
            if (null != borthorParent && borthorParent.isRed()) {
                // 单纯的变色
                param.getParent().setRed(false); // 父节点变色
                borthorParent.setRed(false); // 本身对象变色
                if(null != param.getParent() && null != param.getParent().getParent()) param.getParent().getParent().setRed(true); // 祖父节点变色
                // 指针指向插入节点的祖父节点
                param = param.getParent().getParent();
            } else {
                // 插入节点是是父节点的右子节点
                if ((!param.isLeftNode() && param.getParent().isLeftNode()) || (param.isLeftNode() && !param.getParent().isLeftNode())) {
                    // 父节点左旋
                    rotate(param);
                }
                // 插入节点是是父节点的左节点
                param.getParent().setRed(false); // 父节点变色
                if(null != param.getParent() && null != param.getParent().getParent()) param.getParent().getParent().setRed(true); // 祖父节点变色
                // 祖父节点右旋
                rotate(param.getParent());
            }
        }
    }

    /**
     * 旋转操作
     */
    public void rotate(Node param){
        // 判断是否是左节点
        boolean isLeft = param.isLeftNode();
        // 父节点
        Node parent = param.getParent();
        // 旋转操作
        if (isLeft){
            // 右旋的子节点变化
            if(null != parent && null != parent.getParent()) parent.getParent().setLeft(param); // 祖父链接改成对象节点
            if(null != parent) parent.setLeft(param.getRight()); // 父节点的子节点变化
            param.setRight(parent); // 节点的子节点变化
        } else {
            // 左旋
            if(null != parent && null != parent.getParent()) parent.getParent().setRight(param); // 祖父链接改成对象节点
            if(null != parent) parent.setRight(param.getLeft()); // 父节点的子节点变化
            param.setLeft(parent); // 节点
        }
        if(null != parent && this.root == parent) {
            this.root = param;
        }
    }

    /**
     * 寻找子节点
     */
    private Node findLeafNode(Node root, Node param) {
        if (root.getValue() >= param.getValue()) {
            // 小于，左节点
            if (null != root.getLeft()) {
                return findLeafNode(root.getLeft(), param);
            } else {
                return root;
            }
        } else {
            // 大于，右节点
            if (null != root.getRight()) {
                return findLeafNode(root.getRight(), param);
            } else {
                return root;
            }
        }
    }

    /**
     * 节点显示
     */
    public void show() {
        // 当前层级的点
        List<Node> listNode = new ArrayList<>();
        // 下层的点
        List<Node> listNextNode = new ArrayList<>();
        // 初始化
        listNode.add(this.root);
        // 层级
        int level = 1;
        // 一直循环
        while (1 == 1) {
            for (int i = 0; i < listNode.size(); i++) {
                System.out.print(String.format("%03d", level) + " - ");
                for (int j = 0; j < level; j++) {
                    System.out.print("  ");
                }
                System.out.println(String.format(listNode.get(i).toString()));
                if(null != listNode.get(i).getLeft()) { listNextNode.add(listNode.get(i).getLeft()); }
                if(null != listNode.get(i).getRight()) { listNextNode.add(listNode.get(i).getRight()); }
            }
            // 下一步准备
            if (listNextNode.isEmpty()) {
                break;
            } else {
                listNode = listNextNode;
                listNextNode = new ArrayList<>();
            }
            level++;
        }
        System.out.println("=========================================================");
    }
}
